package com.order.www;

import java.util.ArrayList;
import java.util.List;

/**
 * Creared with IntelliJ IDEA.
 * Description:给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字，
 * 例如，给出的三角形如下：
 * [[20],[30,40],[60,50,70],[40,10,80,30]]
 * 最小的从顶部到底部的路径和是20 + 30 + 50 + 10 = 110。
 * 注意：
 * 如果你能只用O（N）的额外的空间来完成这项工作的话，就可以得到附加分，其中N是三角形中的行总数。
 * User:yxd
 * Date:2022-03-23
 * Time:22:23
 */
public class Dp5 {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if(triangle.isEmpty()){
            return 0;
        }
        /*//状态定义F(i,j)：从(0,0)到底部的最短距离
        //状态转移方程：F(i,j) = Math.min(F(i - 1),j),F(i - 1, j - 1)) + array[i,j]
        //初始定义F(0,0) = array[0,0]
        List<List<Integer>> minPathSum = new ArrayList<>();
        for(int i = 0; i < triangle.size(); i++){
            minPathSum.add(new ArrayList<>());
        }
        // F[0][0]初始化
        minPathSum.get(0).add(triangle.get(0).get(0));
        for(int i = 1;i < triangle.size();i ++){
            int count = 0;
            for(int j = 0;j <= i;j ++){
                if(j == 0){
                    count = minPathSum.get(i - 1).get(j);
                }else if(i == j){
                    count = minPathSum.get(i - 1).get(j - 1);
                }else{
                    count = Math.min(minPathSum.get(i - 1).get(j - 1) ,minPathSum.get(i - 1).get(j));
                }
                minPathSum.get(i).add(count + triangle.get(i).get(j));
            }

        }
        int sum = minPathSum.get(triangle.size() - 1).get(0);
        for(int i = 0;i < triangle.size();i ++){
            sum = Math.min(sum,minPathSum.get(minPathSum.size() - 1).get(i));
        }
        return sum;*/
        //状态定义：F(i,j) 从底部此点的最短路径
        //状态转移方程：F(i,j) = Math.min(F(i + 1,j),F(i + 1,j + 1)) + array[i,j]
        //初始值最下面一层的所有值
        List<List<Integer>> minPathSum = new ArrayList<>(triangle);
        int row = minPathSum.size() - 1;
        for(int i = row - 1;i >= 0;i --){
            for(int j = 0;j <= i;j ++){
                int a = Math.min(triangle.get(i + 1).get(j),triangle.get(i + 1).get(j + 1))
                        + triangle.get(i).get(j);
                minPathSum.get(i).set(j,a);
            }
        }
        return minPathSum.get(0).get(0);
    }

}
